package Arrays;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _39_CombinationSum {
    List<List<Integer>> resultList = new ArrayList<>();
    int[] candidates = null;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        Arrays.sort(this.candidates);
        getSum(0,target,new ArrayList<Integer>());
        return resultList;
    }

    public void getSum(int pos, int rest, List<Integer> list) {
        for(int i=pos;i<candidates.length;i++) {
            int res = rest-candidates[i];
            if (res > 0) {
                List<Integer> templist = new ArrayList<>();
                templist.addAll(list);
                templist.add(candidates[i]);
                getSum(i,res,templist);
            } else if (res == 0) {
                list.add(candidates[i]);
                resultList.add(list);
                break;
            } else {
                break;
            }
        }
    }
}
